1. Field of the Invention
The invention relates to transmission of encrypted information over a communications channel, and in particular, to an apparatus and method of reducing overhead in block cipher encryption and decryption without decreasing security of the content of the encrypted information below a desired level. Alternatively, the invention relates to reducing overhead in block cipher operations to produce a pseudo-random number sequence without decreasing security of the sequence. More specifically, this invention has to do with a way of reducing the burden of re-synchronizing a block cipher, regardless of application of the block cipher, without having to unduly sacrifice overall cycle length.
2. Problems in the Art
The need for secure communications systems continues to expand. It is many times desirable to keep data confidential from both innocent or intentional interlopers or viewers. It is also true of communications of voice.
Most communication of intelligible information is based on alphabetic or numeric systems. Therefore, the content of most data or voice messages is in one sense initially "coded". The English alphabet and the decimal number system are examples of such coding. By using the rules of those systems, the content of the data or voice can be immediately interpreted by those who understand the rules of and can "read" the information coded by that particular alphabet or number system. However, because the alphabets and number systems of the world are open and public domain, there is no substantial limitation on who can understand ("decode") the communication, and thus there is no substantial communication security for such.
A variety of methods have been developed to try to keep knowledge of the content of the information away from certain persons or entities. One example of a secure communications system is set forth in U.S. Pat. No. 4,893,339. Encryption is a well-known method of securing information. Encryption transforms the coded information into a form that is unintelligible when using the normal rules of the particular alphabet or number system originally used for that information.
A variety of encryption methods have been developed. Many function to output information that is made up of the same types of individual characters (letters or numbers) used to code the original intelligible message, but the output is unintelligible. Many operate at a digital level. The original intelligible coded information (e.g. alphanumeric words) is converted into digital words (e.g. bytes), with each character of each word being coded into a set of individual digital values (e.g. bits). Another example is audio (e.g. voice). Voice is converted to an analog electrical signal through a microphone. The analog signal is sampled. The samples are digitized by quantifying each sample digitally. Sections of audio (e.g. frames) can then be digitally quantified and used to reconstruct the analog signal.
In the above examples, the information can be immediately interpreted by those that intercept it by using compatible equipment, or by applying widely known techniques to make it intelligible. Therefore, many encryption methods concentrate on ways to make it difficult or practically impossible to derive the true meaning of the information from the encrypted communication.
One commonly used encryption method is called block cipher. The art of block ciphers is well known. The Data Encryption Standard (DES) is a common example of a block cipher, which is described in Federal Information Processing Standard FIPS-46-2, published by the National Institute of Standards and Technology. Furthermore, methods of using block ciphers to protect information are also well know. FIPS-81 describes methods of using DES in four different modes. FIPS-46-2 and FIPS-81 are incorporated by reference herein.
In conventional block cipher systems, the information to be encrypted is digitized. It can be digitally encoded data or voice (audio). This original, intelligible information is many times referred to as "plaintext", connoting that it contains the information that is intelligible and meaningful, i.e. it contains the message in an understandable form when decoded by easy methods. Block cipher systems tend to take chunks of digitally encoded information (fixed size sets of bits called "blocks") and combine each block with a block created by a pseudo-random number generator. The combined block, known as "ciphertext", is then unintelligible if decoded using conventional decoding techniques, unless it first is decrypted. This requires the receiving party to know ahead of time the identical pseudo-random number block used to transform the plaintext block to a ciphertext block. In communications systems, this means that the transmitter must tell the receiver certain information, apart from the message itself, to allow the receiver to know how to decrypt the message. Sources such as Schneier, Bruce, Applied Cryptography, Second Edition, John Wiley & Sons (1996) provide a discussion of cryptography and random numbers and their generation, and is incorporated by reference herein.
When using a cipher to protect communications traffic, certain features are highly desirable. First, the amount of overhead should be minimal. Overhead is data which is required for purposes other than that of sending the desired message, and may be necessary for such things as keeping the cipher at the receiving end in synchronization with the cipher at the transmitting end. Thus, overhead uses up room or bandwidth in a communication. More throughput of the actual message to be communicated can be achieved by minimizing overhead.
Second, the cipher should have a very long cycle before it begins to repeat itself. The overall cycle length refers to the number of pseudo-random bits a cipher can produce before repeating itself. Generally, the longer the overall cycle length, the more secure the cipher, because there are more possible bit combinations for each time a combination is generated. This is widely known and discussed in the Schneier book referenced above.
Of the various modes of operating a block cipher, cipher feedback (CFB) and output feedback (OFB) are the most popular for use in communications applications. One way in which CFB and OFB block ciphers are used is to input plaintext (containing the actual message to be communicated) into the block cipher. The output would be the ciphertext of the message to be communicated. Another use of these types of block ciphers is as a pseudo-random number generator. The pseudo-random numbers which are generated can be used to then encrypt digital data that contains the message to be communicated. The pseudo-random numbers could also be used for other purposes. For example, the pseudo-random number stream could be used as a rolling code for analog scrambling techniques such as frequency hopping, frequency inversion, or spectral rotation.
It is the use of a block cipher as a pseudo-random number generator (PRNG) that is addressed herein. The input to the block cipher will still be referred to sometimes as "plaintext" and the output "ciphertext", but it is to be understood that it is the output of the block cipher that is a secure pseudo-random number stream. In digital encryption, for example, when combined with digital data comprising a message, it creates the ultimate encrypted data message. This description will mainly discuss use as a PRNG in digital encryption, but it is not limited to such uses.
A block cipher makes an excellent pseudo-random number generator (PRNG) because it has a very long cycle time, offers many possible output sequences which are key dependent, and is totally deterministic, so that it is easy to construct multiple PRNGs which yield identical pseudo-noise or pseudo-random number (PN) bit streams. Furthermore, it is valuable, in the context of creating a high quality pseudo-random number stream that it also can be generated with high accuracy at a number of devices, either transmitters or receivers or both. Therefore, it is useful in such applications as telephone or radio systems where one or more receiving devices must generate the same pseudo-random number stream as the transmitting device.
When using a block cipher as a PRNG over a communications channel, it is critically important to establish and maintain precise synchronization at the bit level between the transmitter and the receiver. This is necessary because if the PRNGs are off by as little as one bit, the sequences produced will be out of synchronization (or "sync") and thus are useless for any application.
Frequently, one will use a PRNG to generate a PN sequence which can then be exclusive OR'ed (XORed) with some plaintext to yield ciphertext. In such an application, the PN bit stream is referred to as a keystream, which is not to be confused with the actual key used in the block cipher itself, which is also frequently referred to as the crypto variable (CV). An example of such an application is DES operating in OFB mode. In this case, DES is used to repeatedly encrypt an initialization vector (IV), with the resulting keystream being used to encrypt plaintext data. OFB mode operation of DES is well documented in a number of sources, including FIPS-81.
One primary problem with DES (or any block cipher) operating in OFB mode is that in addition to the requirement that both the transmitter and receiver must know the secret key or CV, they must also know the IV completely. This can be a problem when a cipher is used in a communications application. Consider a secure communications environment involving radio communications, where there is ordinarily one transmitter and many receivers. Frequently, some of the receivers will be unable to receive the beginning of a given message. If the message is encrypted, and if an initialization vector is sent only at the beginning of the message, then any receiver that misses the IV will be unable to decrypt the message. A prior art solution to this problem is to generate new IVs periodically throughout the message and send them, so that a receiver which did not receive the initial IV will be able to receive one of the subsequent IVs transmitted throughout the remainder of the message.
The ability of a receiver to join into a conversation already in progress is known in the art as late entry. Late entry allows a receiver to join or re-join a secure conversation in case sync has been lost or has never been initially acquired. Thus, in order to facilitate late entry when using a cipher in output feedback mode, it is simply necessary to transmit an initialization vector at periodic intervals throughout the message. In order for the IV to be useful to the receiver, it must be free of bit errors which are often caused by a noisy communications channel. Communicating the IV error-free between the transmitter and receiver is a significant burden in many systems. This is because the length of the IV is the length of the block for the block cipher. In the case of DES, many times this length is 64 bits. So for DES, a 64-bit IV will need to be sent at the beginning of a conversation, and periodically throughout the conversation at the points where late entry is desired. Of course, the IV must be received error-free, or the receiver will fail to construct the proper keystream and will thus be unable to decrypt the secure traffic.
Prior art systems have all required an error free IV to be transmitted periodically throughout the message in order to facilitate late entry. Because this can add a significant amount of overhead to a communications channel, it may require the use of error correcting codes, which can add further burden or overhead to the system, as can other techniques to try to make sure there are no errors, or errors are corrected or compensated, with respect to IV.
As can be appreciated, by repeating the IV throughout a message, overhead is increased. Also, there are a number of known methods in the art to attempt to ensure that the IV is received accurately by the receiver. However, such methods add additional overhead to the system. To greatly increase the probability of accurate receipt of IV, increasingly complex methods could be applied, but the increase in overhead would substantially increase the amount of room taken up in the communication and make it slower and more cumbersome.
Moreover, security of block cipher encryption is normally tied to length of IV. The longer the IV, the less susceptible the encryption is to attack. This is well known and documented. As mentioned previously, however, for the authorized intended recipient(s) of the transmitted message to actually receive it and be able to use it, the IV must be received bit by bit totally accurate. Although there are ways to make the transmitter and receiver both know IV without error, it is more difficult the longer the IV, especially under communications channel transmission conditions.
While many secure systems operate under ideal conditions, e.g. where the communications link does not create conditions that could corrupt the transmitted information, in normal conditions the channel will create such problems.
In DES, the IV's are usually 64 bits long. But 64 bits is a long sequence to receive error free, especially over a communications channel and more so over a less than ideal communications channel. As stated above, such things as forward error correcting (FEC) codes are used in the prior art to increase the odds that the IV being used is accurate, but such methods add appreciably to overhead.
It is known from statistical analysis that if the length of IV were reduced, the probability of errors would decrease. However, as mentioned above, the security of an encryption method is related to length of IV. If the length were reduced to decrease probability of error in the transmitted IV for cryptographic synchronization or crypto sync, the security of the encryption would also decrease. This may be unacceptable.
U.S. Pat. No. 4,322,576 discusses IV's, their 64 bit length and cryptographic sync, and recognizes the space the IV's take up. Its solution is to place IV at a different place in the transmission to attempt to take advantage of what it calls lulls in the encryption/decryption process. However, IV is still 64 bits long.
U.S. Pat. No. 4,7575,536 discusses 64-bit IV's in DES, implemented in a digital signal processor (DSP) and operating in output feedback (OFB) mode, with a cycle length of 2.sup.64.
U.S. Pat. No. 5,195,136 discloses use of linear feedback shift registers with cipher block chaining mode for DES, and addresses errors caused by noisy channels, but does not address shortening the length of IV.
Therefore, there is a seemingly unsolveable dilemma, especially with respect to generating PN streams for use in securing data using block cipher techniques. Thus, there is real need in the art to decrease overhead associated with IV for initiating, maintaining and reacquiring cryptographic sync between transmitting and receiving units using a block cipher, but doing so without reduction in security, or at least, with an acceptable amount of decrease in security.
It is therefore a primary object of the present invention to provide an apparatus and method for reducing the overhead in a block cipher system without reducing the security of the PN stream or communication, and which improves over and solves the problems and deficiencies in the art.
Further objects, features, and advantages of the present invention include an apparatus and method as above-described which:
1. provides for late entry but with less overhead burden. PA1 2. provides for late entry with less overhead burden but without reducing the overall cycle time of the block cipher. PA1 3. is flexible and adaptable in its application and use, including both analog and digital uses and different uses of PN streams. PA1 4. applies to a variety of block cipher and PRNG types and uses. PA1 5. is especially useful when communicating information over a communications channel that is less than ideal with respect to possible corruption of the information being transmitted. PA1 6. can reduce synchronization errors even in less than ideal communications channels. PA1 7. can achieve and maintain cryptographic synchronization even when initialization vectors are partially or wholly destroyed by channel conditions or burst errors. PA1 8. can be adapted to achieve varying degrees of fading protection.
These and other objects, features and advantages of the present invention will become more apparent with reference to the accompanying specification and claims.